Block-based motion compensation techniques including either motion interpolation or motion prediction are used in digital image sequence coding to reduce the amount of data that must be transmitted in digital video systems. Video sequences typically exhibit a substantial amount of repetitive image information between consecutive frames. By compensating for the motion of objects within an image frame, a high compression of the video data can be achieved.
Block-based motion compensation techniques initially divide a video frame into several blocks of picture elements (pels). These techniques employ motion vectors to indicate the movement of these blocks between successive frames. It is assumed that each pel within a block has the same translational motion. These motion vectors, along with error signals, may be transmitted to a receiver. The receiver may then regenerate the video blocks using the motion vectors to locate the corresponding blocks from a previously transmitted frame. The error signals are used to account for pel differences within each block between successive frames.
Consider, for example, the image of a football in a football game video sequence. The football image remains substantially identical from frame to frame, but its location within the video frame changes. If the motion vector of the football is known, then the image of the football can be reconstructed in a new video frame using the football image data from the previous frame. As a consequence, instead of transmitting repetitive image data for each new frame, motion vectors may be transmitted. An error signal is also transmitted to account for other differences, for example, a change in orientation of the football.
Motion compensation methods employ a process known as motion estimation to generate the motion vectors. In motion estimation, a motion vector for a particular block within a current frame is determined by matching the image data within the block to the image data in a displaced block within a reference frame. The motion vector represents the difference in position between the block from the current frame and the displaced block from the reference frame. The reference frame may be a previous frame, as in motion compensation prediction techniques, or a previous or future frame, as in motion compensation interpolation techniques.
To effect such block matching, the entire reference frame is not ordinarily searched for the displaced block, as such a search can consume considerable computation power and time. Instead, a search window is defined within the reference frame.
In motion estimation, a search window may be defined in terms of its size in pels and its location within the reference frame. In determining search window location, it is known in the art to center the search window on the position of the block to be matched. The method assumes that an image within a video block is most likely to be found in the vicinity of its location in a previous or subsequent frame. The search window size is then optimally chosen to be as large as the sum of the block size and the maximum probable block movement in any direction. For example, for a 15.times.15 pel block capable of moving up to 5 pels in any direction between frames, the maximum search window size would be 25.times.25 pels.
Referring again to the analogy of a football within a football game video sequence, the football may, for discussion purposes, represent a block of video data. To find a displaced football in a reference frame, a motion estimation method would initially define a search window within which it would expect to find the football image in the reference frame. The search window is then scanned for the image within the window most resembling the football. Once the football image is found, a motion vector may be calculated for the football describing its movement between the reference frame and the present frame.
Under such methods of locating the search window, however, the search window size used for block matching limits the range of motion that may be compensated for. In the 25.times.25 pel search window defined above, block motion of more than 6 pels cannot be successfully compensated. If the motion estimation method fails to find the proper displaced block, a large error signal will have to be transmitted, and the advantages of motion compensation will be greatly reduced.
To increase the range of motion which may be compensated for, it is well known that the search window size may be enlarged in order to account for greater image movement. The use of larger search windows, however, consumes more computation time and power because there are more candidate displaced blocks to evaluate to effect block matching. For example, if an exhaustive search is used to effect block matching, an increase in size of a 25.times.25 search window by a single pel in each direction will increase the number of candidate displaced blocks by 27.sup.2 -25.sup.2 =104 blocks.
Several attempts have been made to increase the range of motion which may be compensated for without drastically increasing the computational load. It is well known in the art to employ search algorithms which are faster than an exhaustive search. These algorithms include the hierarchical search, the logarithmic search, and conjugate direction search. Because motion estimation techniques using such algorithms greatly reduce the number of calculations required for block matching, they may employ larger search windows than an exhaustive search routine.
The faster search techniques, however, are not guaranteed to find the proper displaced block. In other words, these algorithms may not find the best match for a particular block to be coded, which leads to coding inefficiency. Furthermore, such search techniques require complex image data manipulation when compared with the exhaustive search. The complex image data manipulation may also computationally load the system.